package main

import "fmt"

// String A = "tutorialhorizon";

// String B = "dynamictutorialProgramming";

// Output: Length of Longest Common Substring: 8 ("tutorial").

// 								b
//             ""d y n a m i c t u t o r i a l P r o g r a m m i n g
//         ""  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
// 		t	0
// 		u	0
// 		t	0
// a	o	0
// 		r	0
// 		i	0
// 		a	0
// 		l	0
// i represent ith letter from string 1
// j represent jth letter from string 2
// dp(i,j) means the longest length of the common subarray
// dp[i][j] = {
// 	if (a[i] == b[j])  -> dp[i-1][j-1] +1
// }

// 	   "" a b c d
// ""  0  0 0 0 0
// a   0  1 0 0 0
// b   0  0 2
// c   0  0
func longestCommonSubarray(a, b string) int {
	res := -1
	lenA, lenB := len(a), len(b)
	dp := make([][]int, lenA+1)
	for i := 0; i <= lenA; i++ {
		dp[i] = make([]int, lenB+1)
	}
	for i := 1; i <= lenA; i++ {
		for j := 1; j <= lenB; j++ {
			if a[i-1] == b[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				if dp[i][j] > res {
					res = dp[i][j]
				}
			}
		}
	}
	// fmt.Println(dp)
	return res
}

// [
//   ["3234.html", "xys.html", "7hsaa.html"], // user1
//   ["3234.html", "sdhsfjdsh.html", "xys.html", "7hsaa.html"] // user2
// ]
// 						                user2
// user1				""	"3234.html"		"sdhsfjdsh.html"	"xys.html"	"7hsaa.html"
// 			""			0	0				0					0			0
// 		"3234.html"		0	1				0					0			0
// 		"xys.html"		0	0				0					1			0
// 		"7hsaa.html"	0	0				0					0			2
func longestCommonContinuousSubArray(a, b []string) []string {
	res := []string{}
	longest := 0
	lenA, lenB := len(a), len(b)

	dp := make([][]int, lenA+1)
	for i := 0; i <= lenA; i++ {
		dp[i] = make([]int, lenB+1)
	}

	for i := 1; i <= lenA; i++ {
		for j := 1; j <= lenB; j++ {
			if a[i-1] == b[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				if dp[i][j] > longest {
					longest = dp[i][j]
					res = a[i-longest : i]
				}
			}
		}
	}
	// fmt.Println(res)
	return res
}

func main() {
	a := "tutorialhorizon"
	b := "dynamictutorialProgramming"
	fmt.Println(longestCommonSubarray(a, b))
	x := []string{"3234.html", "xys.html", "7hsaa.html"}
	y := []string{"3234.html", "sdhsfjdsh.html", "xys.html", "7hsaa.html"}
	fmt.Println(longestCommonContinuousSubArray(x, y))
}
